package leetcode_121_140;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class sumNumbers_129 {
    /**
     * 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
     * 每条从根节点到叶节点的路径都代表一个数字：
     *
     * 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
     * 计算从根节点到叶节点生成的 所有数字之和 。
     *
     * 叶节点 是指没有子节点的节点。
     */
    public int sumNumbers(TreeNode root) {
        /**
         * 思路，使用集合记录所有产生的数字
         * 1ms
         */
        nums=new ArrayList<>();
        function(root);
        int ans=0,count;
        for(int i=0;i<nums.size();i++){
            count=1;
            for(int t=0;t<nums.get(i).size();t++){
                ans+=nums.get(i).get(nums.get(i).size()-1-t)*count;
                count*=10;
            }
        }
        return ans;
    }
    List<List<Integer>>nums=new ArrayList<>();  //数字集合

    List<Integer>num=new ArrayList<>();  //实时数字
    private void function(TreeNode root){
        num.add(root.val);
        if(root.left==null && root.right==null){  //本身就是叶子节点
            nums.add(new ArrayList<>(num));
            return ;
        }
        if (root.left != null) {
            function(root.left);
            num.remove(num.size() - 1);
        }
        if (root.right != null) {
            function(root.right);
            num.remove(num.size() - 1);
        }
    }


    /**
     * 高解
     */
    public int sumNumbers2(TreeNode root) {
        return helper(root, 0);
    }

    public int helper(TreeNode root, int i){
        if (root == null) return 0;
        int temp = i * 10 + root.val;
        if (root.left == null && root.right == null)
            return temp;
        return helper(root.left, temp) + helper(root.right, temp);
    }

}
